package sort;

public class Quicksort implements ISort {
	private int[] elements;
	
	public void doSort(int[] elements) {
		if(elements == null || elements.length == 0) {
			return;
		}
		
		this.elements = elements;
		quicksort(0, elements.length - 1);
	}
	
	private void quicksort(int low, int high) {
		int i = low;
		int j = high;
		
		int pivot = elements[low + (high - low) / 2];
		while(i <= j) {
			while(elements[i] < pivot) {
				i++;
			}
			
			while(elements[j] > pivot) {
				j--;
			}
			
			if(i <= j) {
				swap(i, j);
				i++;
				j--;
			}
		}
		
		if(low < j) {
			quicksort(low, j);
		}
		
		if(i < high) {
			quicksort(i, high);
		}
	}
	
	private void swap(int i, int j) {
		int tmp = elements[i];
		elements[i] = elements[j];
		elements[j] = tmp;
	}
}
